package LinkedList;

import java.util.HashSet;
import java.util.Set;

/**
 * 使用HashSet存储已经遍历的节点，set的特点是无序不重复的元素
 * 而且如果使用add方法添加同一值，会自动覆盖之前添加的值，因此很适合本题
 * 如果使用contains()方法发现已经有了这个值，证明到了环形的入口
 */
public class DetectCycle {
    public static void main(String[] args) {

    }
    public ListNode detectCycle(ListNode head){
        Set<ListNode> nodeSet=new HashSet<ListNode>();
        ListNode curNode=head;
        while(curNode!=null){
            if(nodeSet.contains(curNode)){
                return curNode;
            }
            else {
                nodeSet.add(curNode);
            }
            curNode=curNode.next;
        }
        return null;
    }

    public boolean detectCycle1(ListNode head){
        Set<ListNode> nodeSet=new HashSet<ListNode>();
        ListNode curNode=head;
        while(curNode!=null){
            if(nodeSet.contains(curNode)){
                return true;
            }
            else {
                nodeSet.add(curNode);
            }
            curNode=curNode.next;
        }
        return false;
    }
}
